home *** CD-ROM | disk | FTP | other *** search
/ Apple WWDC 1996 / WWDC96_1996 (CD).toast / Technology Materials / MacApp Release 10 / MacApp Release 10 - HD Ready / Libraries / Core / Sources / UDynamicArray.cp < prev    next >
Encoding:
Text File  |  1996-04-03  |  22.8 KB  |  788 lines  |  [TEXT/MPS ]
  1. //----------------------------------------------------------------------------------------
  2. // UDynamicArray.cp 
  3. // Copyright © 1986-96 by Apple Computer, Inc. All rights reserved.
  4. //----------------------------------------------------------------------------------------
  5.  
  6. #ifndef __UDYNAMICARRAY__
  7. #include "UDynamicArray.h"
  8. #endif
  9.  
  10. // MacApp
  11.  
  12. #ifndef __UFAILURE__
  13. #include "UFailure.h"
  14. #endif
  15.  
  16. #ifndef __ULISTITERATOR__
  17. #include "UListIterator.h"
  18. #endif
  19.  
  20. #ifndef __UCOREUTILITIES__
  21. #include "UCoreUtilities.h"
  22. #endif
  23.  
  24. #ifndef __UMEMORY__
  25. #include "UMemory.h"
  26. #endif
  27.  
  28. #ifndef __USTREAM__
  29. #include "UStream.h"
  30. #endif
  31.  
  32.  
  33. // OpenDoc
  34.  
  35. #ifndef _MEMMGR_
  36. #include "MemMgr.h"
  37. #endif
  38.  
  39.  
  40. // Toolbox
  41.  
  42. #ifndef __PACKAGES__
  43. #include <Packages.h>
  44. #endif
  45.  
  46. // ANSI
  47.  
  48. #ifndef __STDIO__
  49. #include <stdio.h>
  50. #endif
  51.  
  52. #ifndef __STDLIB__
  53. #include <stdlib.h>
  54. #endif
  55.  
  56.  
  57. //========================================================================================
  58. // GLOBAL Procedures
  59. //========================================================================================
  60. static CompareResult TestItemForInsert(ArrayIndex anItem,
  61.                                        void* yourDataPtr);
  62.  
  63. static CompareResult CompareElements(void* element1,
  64.                                     void* element2,
  65.                                     void* yourDataPtr);
  66.  
  67. static ArrayIndex RandomArrayIndex(ArrayIndex beginIndex,
  68.                                    ArrayIndex endIndex);
  69.  
  70. //========================================================================================
  71. // CLASS TDynamicArray
  72. //========================================================================================
  73. #undef Inherited
  74. #define Inherited TObject
  75.  
  76. #pragma segment ListNonRes
  77. MA_DEFINE_CLASS_M1(TDynamicArray,
  78.                    Inherited);
  79.  
  80. //----------------------------------------------------------------------------------------
  81. // TDynamicArray constructor
  82. //----------------------------------------------------------------------------------------
  83. #pragma segment ListRes
  84.  
  85. TDynamicArray::TDynamicArray() :
  86.     fIteratorPtr(NULL),
  87.  
  88.     fAllocatedSize(kEmptyIndex),
  89.     fAllocationIncrement(kAllocationIncrement),
  90.     fElementSize(1),
  91.     fElementSizeShift(0),
  92.     fFreeRequested(FALSE),
  93.     fSize(kEmptyIndex),
  94.     fArraySpace(NULL)
  95. {
  96. }
  97.  
  98. //----------------------------------------------------------------------------------------
  99. // TDynamicArray destructor
  100. //----------------------------------------------------------------------------------------
  101. #pragma segment MADestructorRes
  102.  
  103. TDynamicArray::~TDynamicArray()
  104. {
  105. }
  106.  
  107. //----------------------------------------------------------------------------------------
  108. // TDynamicArray::IDynamicArray: 
  109. //----------------------------------------------------------------------------------------
  110. #pragma segment ListRes
  111.  
  112. void TDynamicArray::IDynamicArray(ArrayIndex initialSize,
  113.                                   short elementSize)
  114. {
  115.     IObject();
  116.  
  117. #if qDebug
  118.     if (initialSize < kEmptyIndex)
  119.     {
  120.         ProgramBreak("initialSize must be non-negative!");
  121.         initialSize = kEmptyIndex;
  122.     }
  123.  
  124.     if (elementSize <= 0)
  125.     {
  126.         ProgramBreak("In TDynamicArray.IDynamicArray: preposterous element size. (zero or negative)");
  127.         Failure(minErr, 0);
  128.     }
  129. #endif
  130.  
  131.     fSize = kEmptyIndex;
  132.  
  133.     fElementSize = elementSize;
  134.     fAllocatedSize = kEmptyIndex;
  135.  
  136.     // calculate the elementsizeshift that represents the nearest power of 2 
  137.     fElementSizeShift = 0;
  138.     while (((elementSize - 1) >> fElementSizeShift) > 0)
  139.         ++fElementSizeShift;
  140.  
  141.     FailInfo fi;
  142.     Try(fi)
  143.     {
  144.         SetArraySize(initialSize);
  145.         fi.Success();
  146.     }
  147.     else
  148.     {
  149.         Free();
  150.         fi.ReSignal();
  151.     }
  152. }
  153.  
  154. //----------------------------------------------------------------------------------------
  155. // TDynamicArray::Clone: 
  156. //----------------------------------------------------------------------------------------
  157. #pragma segment ListRes
  158.  
  159. TObject* TDynamicArray::Clone()
  160. {
  161.     MAVolatileInit(TDynamicArray * , aClonedDynamicArray, (TDynamicArray *)(Inherited::Clone()));
  162.  
  163.     aClonedDynamicArray->fIteratorPtr = NULL;
  164.     aClonedDynamicArray->fArraySpace = NULL;
  165.  
  166.     FailInfo fi;
  167.     Try(fi)
  168.     {
  169.         long itsSize = (long)MMBlockSize(fArraySpace);
  170.         Ptr newVal = (Ptr)new
  171.                     char[itsSize];
  172.  
  173.         MABlockMove(fArraySpace, newVal, itsSize);
  174.  
  175.         aClonedDynamicArray->fArraySpace = newVal;
  176.         fi.Success();
  177.     }
  178.     else
  179.     {
  180.         aClonedDynamicArray->Free();
  181.  
  182.         fi.ReSignal();
  183.     }
  184.  
  185.     return aClonedDynamicArray;
  186. }
  187.  
  188. //----------------------------------------------------------------------------------------
  189. // TDynamicArray::ReadFrom: 
  190. //----------------------------------------------------------------------------------------
  191. #pragma segment MAReadResource
  192.  
  193. void TDynamicArray::ReadFrom(TStream* aStream)
  194. {
  195.     Inherited::ReadFrom(aStream);
  196.  
  197.     fElementSize = aStream->ReadInteger();
  198.     fElementSizeShift = aStream->ReadInteger();
  199.     fAllocationIncrement = aStream->ReadLong();
  200.  
  201.     FailInfo fi;
  202.     Try(fi)
  203.     {
  204.         SetArraySize(0);
  205.         fi.Success();
  206.     }
  207.     else
  208.     {
  209.         Free();
  210.         fi.ReSignal();
  211.     }
  212.  
  213. }
  214.  
  215. //----------------------------------------------------------------------------------------
  216. // TDynamicArray::WriteTo: 
  217. //----------------------------------------------------------------------------------------
  218. #pragma segment MAWriteResource
  219.  
  220. void TDynamicArray::WriteTo(TStream* aStream)
  221. {
  222.     Inherited::WriteTo(aStream);
  223.  
  224.     aStream->WriteInteger(fElementSize);
  225.     aStream->WriteInteger(fElementSizeShift);
  226.     aStream->WriteLong(fAllocationIncrement);
  227. }
  228.  
  229. //----------------------------------------------------------------------------------------
  230. // TDynamicArray::operator[]: 
  231. //----------------------------------------------------------------------------------------
  232. #pragma segment ListRes
  233.  
  234. void* TDynamicArray::operator[](ArrayIndex index) const
  235. {
  236.     return fArraySpace + (index << fElementSizeShift);
  237. }
  238.  
  239. //----------------------------------------------------------------------------------------
  240. // TDynamicArray::ComputeAddress: 
  241. //----------------------------------------------------------------------------------------
  242. #pragma segment ListRes
  243.  
  244. void* TDynamicArray::ComputeAddress(ArrayIndex index) const
  245. {
  246.     return fArraySpace + ((index - 1) << fElementSizeShift);
  247. }
  248.  
  249. //----------------------------------------------------------------------------------------
  250. // TDynamicArray::DeleteElementsAt: 
  251. //----------------------------------------------------------------------------------------
  252. #pragma segment ListRes
  253.  
  254. void TDynamicArray::DeleteElementsAt(ArrayIndex index,
  255.                                      ArrayIndex count)
  256. {
  257. #if qRangeCheck
  258.     if ((index < 1) || (index > fSize))
  259.     {
  260. #if qDebugMsg
  261.         fprintf(stderr, "fSize == %1d  index == %1d\n", fSize, index);
  262. #endif
  263.  
  264.         ProgramBreak("Range Check in TDynamicArray.DeleteElementsAt");
  265.     }
  266. #endif
  267.  
  268.     ArrayIndex countBytes = count << fElementSizeShift;
  269.  
  270.     void* indexPtr = ComputeAddress(index);
  271.     void* nextElementPtr = ComputeAddress(index + count);
  272.     void* lastElementPtr = ComputeAddress(fSize + 1);
  273.  
  274.     if (nextElementPtr < lastElementPtr)        // deleted from middle? Compress the array 
  275.         MABlockMoveOverlap(nextElementPtr, indexPtr, (long)lastElementPtr - (long)nextElementPtr);
  276.  
  277. #if qDebug
  278.     BlockSet((Ptr)((long)lastElementPtr - countBytes), countBytes, kResizedInitVal);
  279. #endif
  280.  
  281.     SetArraySize(fSize - count);                // take up slack if necessary. Should never
  282.     // Fail when shrinking array.
  283.     fSize -= count;
  284.  
  285.     if (fIteratorPtr)                            // Keep all iterations apprised
  286.         fIteratorPtr->DeleteElementAt(index, count);
  287. }
  288.  
  289. //----------------------------------------------------------------------------------------
  290. // TDynamicArray::DeleteAll: 
  291. //----------------------------------------------------------------------------------------
  292. #pragma segment ListRes
  293.  
  294. void TDynamicArray::DeleteAll()
  295. {
  296.     if (fSize)
  297.         DeleteElementsAt(1, fSize);
  298. }
  299.  
  300. //----------------------------------------------------------------------------------------
  301. // TDynamicArray::GetElementsAt: 
  302. //----------------------------------------------------------------------------------------
  303. #pragma segment ListRes
  304.  
  305. void TDynamicArray::GetElementsAt(ArrayIndex index,
  306.                                   void* ElementPtr,
  307.                                   ArrayIndex count)
  308. {
  309. #if qRangeCheck
  310.     if ((index < 1) || (index > fSize))
  311.     {
  312. #if qDebugMsg
  313.         fprintf(stderr, "fSize == %1d  index == %1d\n", fSize, index);
  314. #endif
  315.  
  316.         ProgramBreak("Range Check in TDynamicArray::GetElementsAt");
  317.     }
  318. #endif
  319.  
  320.     // The count computation for this move makes sure that if the element size is not
  321.     // a power of 2 that we don't copy more bytes back to the caller than required for a
  322.     // given number of elements sending the caller into orbit and heading straight for the
  323.     // Excedrin.
  324.  
  325.     // !!! NOTE MULTIPLE (> 1) element moves for non-power of 2 element sizes are not yet
  326.     // supported!
  327.  
  328.     if (count > kEmptyIndex)
  329.         MABlockMove(ComputeAddress(index), (Ptr)ElementPtr, ((count - 1) << fElementSizeShift) + fElementSize);
  330. }
  331.  
  332. //----------------------------------------------------------------------------------------
  333. // TDynamicArray::Free: 
  334. //----------------------------------------------------------------------------------------
  335. #pragma segment ListRes
  336.  
  337. void TDynamicArray::Free()
  338. {
  339.     // She can't do it cap'n. The dilithium crystals are burrrrnt out! If they're
  340.     // allowed to rest a while they might recover enough for another try.
  341.     if (fIteratorPtr)
  342.     {
  343.         fFreeRequested = TRUE;
  344.         DeleteAll();
  345.     }
  346.     else
  347.     {
  348.         delete fArraySpace;
  349.         fArraySpace = NULL;
  350.  
  351.         Inherited::Free();
  352.     }
  353. }
  354.  
  355. //----------------------------------------------------------------------------------------
  356. // TDynamicArray::InsertElementsBefore: 
  357. //----------------------------------------------------------------------------------------
  358. #pragma segment ListRes
  359.  
  360. void TDynamicArray::InsertElementsBefore(ArrayIndex index,
  361.                                          const void* ElementPtr,
  362.                                          ArrayIndex count)
  363. {
  364. #if qRangeCheck
  365.     if ((index < 1) || (index > fSize + 1))
  366.     {
  367. #if qDebugMsg
  368.         fprintf(stderr, "fSize == %1d  index == %1d\n", fSize, index);
  369. #endif
  370.  
  371.         ProgramBreak("Range Check in TDynamicArray.InsertElementsBefore");
  372.     }
  373. #endif
  374.  
  375.     if (fSize + count > fAllocatedSize)
  376.         SetArraySize(fSize + count);            // make sure there's room if needed 
  377.  
  378.     ArrayIndex countBytes = count << fElementSizeShift;
  379.  
  380.     void* indexPtr = ComputeAddress(index);
  381.     void* nextIndexPtr = ComputeAddress(index + count);
  382.     void* lastElementPtr = ComputeAddress(fSize + 1);
  383.  
  384.     if (index <= fSize)                            // clear out a hole? 
  385.         MABlockMoveOverlap(indexPtr, nextIndexPtr, (long)lastElementPtr - (long)indexPtr);
  386.  
  387.     // !!! we still don't account for multiple element moves with non power of 2 element sizes.
  388.     // Would it be best to create a MoveElements method and put the smarts in it?
  389.  
  390.     if ((countBytes == sizeof(long)) && !odd((Ptr)ElementPtr) && !odd(indexPtr))
  391.         *((long*)indexPtr) = *((long*)ElementPtr);// shortcut for longs 
  392.     else
  393.         MABlockMove((Ptr)ElementPtr, indexPtr, countBytes);// longcut for shorts (and other sizes) 
  394.  
  395.     fSize += count;
  396.  
  397.     if (fIteratorPtr)                            // Keep all iterations apprised
  398.         fIteratorPtr->InsertElementBefore(index, count);
  399. }
  400.  
  401. //----------------------------------------------------------------------------------------
  402. // TDynamicArray::Merge: 
  403. //----------------------------------------------------------------------------------------
  404. #pragma segment ListRes
  405.  
  406. void TDynamicArray::Merge(TDynamicArray* aDynamicArray)
  407. {
  408. #if qDebug
  409.     if ((fElementSize != aDynamicArray->fElementSize) || (fElementSizeShift != aDynamicArray->fElementSizeShift))
  410.         ProgramBreak("In TDynamicArray.Merge: fElementSize or fElementSizeShift don't match with the TDynamicArray to merge!");
  411. #endif
  412.  
  413.     ArrayIndex arraySize = aDynamicArray->GetSize();
  414.     if (arraySize != kEmptyIndex)
  415.     {
  416.         // Force the memory move before the call to ComputeAddress.
  417.         SetArraySize(GetSize() + arraySize);
  418.         InsertElementsBefore(GetSize() + 1, aDynamicArray->ComputeAddress(1), arraySize);
  419.     }
  420. }
  421.  
  422. //----------------------------------------------------------------------------------------
  423. // TDynamicArray::ReplaceElementsAt: 
  424. //----------------------------------------------------------------------------------------
  425. #pragma segment ListRes
  426.  
  427. void TDynamicArray::ReplaceElementsAt(ArrayIndex index,
  428.                                       const void* ElementPtr,
  429.                                       ArrayIndex count)
  430. {
  431. #if qRangeCheck
  432.     if ((index < 1) || (index > fSize))
  433.     {
  434. #if qDebugMsg
  435.         fprintf(stderr, "fSize == %1d  index == %1d\n", fSize, index);
  436. #endif
  437.  
  438.         ProgramBreak("Range Check in TDynamicArray.ReplaceElementsAt");
  439.     }
  440. #endif
  441.  
  442.     MABlockMove((Ptr)ElementPtr, ComputeAddress(index), count << fElementSizeShift);
  443. }
  444.  
  445. //----------------------------------------------------------------------------------------
  446. // TDynamicArray::SetArraySize: 
  447. //----------------------------------------------------------------------------------------
  448. #pragma segment ListRes
  449.  
  450. void TDynamicArray::SetArraySize(ArrayIndex theSize)
  451. {
  452.     ArrayIndex newAllocatedSize;
  453.  
  454.     if (fArraySpace == NULL)
  455.         fArraySpace = new char[0];
  456.  
  457.     if ((theSize > fAllocatedSize) || (fAllocatedSize - theSize >= fAllocationIncrement))
  458.     {
  459. #if qDebug
  460.         if (fAllocationIncrement < 0)
  461.             ProgramBreak("fAllocationIncrement < 0 !  You have serious problems.");
  462. #endif
  463.  
  464.         // Set the # of allocated elements to the nearest multiple of
  465.         // fAllocationIncrement.
  466.         if (fAllocationIncrement)
  467.             newAllocatedSize = (theSize + fAllocationIncrement) - (theSize + fAllocationIncrement) % fAllocationIncrement;
  468.         else
  469.             newAllocatedSize = theSize;
  470.  
  471.         if (newAllocatedSize != fAllocatedSize)
  472.         {
  473.             Ptr newPtr = (Ptr)MMReallocate(fArraySpace, (newAllocatedSize << fElementSizeShift));
  474.             if (newPtr == fArraySpace)        // was not reallocated!
  475.                 Failure(memFullErr, 0);
  476.             else
  477.                 fArraySpace = newPtr;
  478.         }
  479.  
  480.         fAllocatedSize = newAllocatedSize;
  481.     }
  482. }
  483.  
  484. //----------------------------------------------------------------------------------------
  485. // TDynamicArray::CompareElements: 
  486. //----------------------------------------------------------------------------------------
  487. #pragma segment ListRes
  488.  
  489. CompareResult TDynamicArray::CompareElements(void* /* Element1 */, void* /* Element2 */)
  490. {
  491.     // By Default consider all items equal 
  492.     return kItem1EqualItem2;
  493. }
  494.  
  495. //----------------------------------------------------------------------------------------
  496. // TDynamicArray::Sort: 
  497. //----------------------------------------------------------------------------------------
  498. void TDynamicArray::Sort()
  499. {
  500.     if (GetSize() > 0)
  501.     {
  502.         void* swapBuffer = GetSwapBuffer();
  503.         QuickSort(1, fSize, &::CompareElements, this, swapBuffer);
  504.         ReleaseSwapBuffer(swapBuffer);
  505.     }
  506. }
  507.  
  508. //----------------------------------------------------------------------------------------
  509. // TDynamicArray::SortBy: NOTE: This doesn't work with a CompareItems Function that inserts
  510. // or deletes elements.
  511. //----------------------------------------------------------------------------------------
  512. #pragma segment ListRes
  513.  
  514. void TDynamicArray::SortElementsBy(CompareElementsType CompareItems,
  515.                          void* yourDataPtr)
  516. {
  517.     if (GetSize() > 0)
  518.     {
  519.         void* swapBuffer = GetSwapBuffer();
  520.         QuickSort(1, fSize, CompareItems, yourDataPtr, swapBuffer);
  521.         ReleaseSwapBuffer(swapBuffer);
  522.     }
  523. }
  524.  
  525. //----------------------------------------------------------------------------------------
  526. // TDynamicArray::QuickSort: 
  527. //----------------------------------------------------------------------------------------
  528. #pragma segment ListRes
  529. void* TDynamicArray::GetSwapBuffer()
  530. {
  531.     return (fElementSize == sizeof(long)) ? NULL : (void*) new char[fElementSize];
  532. }
  533.  
  534. //----------------------------------------------------------------------------------------
  535. // TDynamicArray::QuickSort: 
  536. //----------------------------------------------------------------------------------------
  537. #pragma segment ListRes
  538. void TDynamicArray::ReleaseSwapBuffer(void* swapBuffer)
  539. {
  540.     if (fElementSize == sizeof(long))
  541.         delete swapBuffer;
  542. }
  543.  
  544. //----------------------------------------------------------------------------------------
  545. // TDynamicArray::QuickSort: 
  546. //----------------------------------------------------------------------------------------
  547. #pragma segment ListRes
  548. void TDynamicArray::SwapElements(void* element1, void* element2, void* swapBuffer)
  549. {
  550.     if (fElementSize == sizeof(long)) // shortcut for longs
  551.     {
  552.         register long swapLong = *(long*)element1;
  553.         *(long*)element1 = *(long*)element2;
  554.         *(long*)element2 = swapLong;
  555.     }
  556.     else
  557.     {
  558.         MABlockMove(element1, swapBuffer, fElementSize);
  559.         MABlockMove(element2, element1, fElementSize);
  560.         MABlockMove(swapBuffer, element2, fElementSize);
  561.     }
  562. }
  563.  
  564. //----------------------------------------------------------------------------------------
  565. // TDynamicArray::QuickSort: 
  566. //----------------------------------------------------------------------------------------
  567. #pragma segment ListRes
  568. void TDynamicArray::QuickSort(ArrayIndex beginIndex,
  569.                             // p
  570.                             ArrayIndex endIndex,
  571.                             // r
  572.                             CompareElementsType CompareItems,
  573.                             void* yourDataPtr,
  574.                             void* swapBuffer)
  575. {
  576.     if (beginIndex < endIndex)
  577.     {
  578.         ArrayIndex left = QSRandomPartition(beginIndex, endIndex, CompareItems, yourDataPtr, swapBuffer);
  579.         QuickSort(beginIndex, left, CompareItems, yourDataPtr, swapBuffer);
  580.         QuickSort(left + 1, endIndex, CompareItems, yourDataPtr, swapBuffer);
  581.     }
  582. }
  583.  
  584. //----------------------------------------------------------------------------------------
  585. // TDynamicArray::QSPartition: 
  586. //----------------------------------------------------------------------------------------
  587. #pragma segment ListRes
  588. ArrayIndex TDynamicArray::QSPartition(ArrayIndex beginIndex, // p
  589.                                     ArrayIndex endIndex, // r
  590.                                     CompareElementsType CompareItems,
  591.                                     void* yourDataPtr,
  592.                                     void* swapBuffer)
  593. {
  594.     if (beginIndex >= endIndex)
  595.         return endIndex;
  596.     {
  597.         void* pivot = ComputeAddress(beginIndex);        // x
  598.         ArrayIndex i = beginIndex - 1;            // p - 1
  599.         ArrayIndex j = endIndex + 1;            // r + 1
  600.         while (TRUE)
  601.         {
  602.             void* secondKey;
  603.             do
  604.             {
  605.                 --j;
  606.                 secondKey = ComputeAddress(j);                // A[j]
  607.             } while (CompareItems(pivot, secondKey, yourDataPtr) <= kItem1LessThanItem2);
  608.  
  609.             do
  610.             {
  611.                 ++i;
  612.                 secondKey = ComputeAddress(i);                // A[i]
  613.             } while (CompareItems(pivot, secondKey, yourDataPtr) >= kItem1GreaterThanItem2);
  614.  
  615.             if (i < j)
  616.             {
  617.                 // Swap the elements
  618.                 SwapElements(ComputeAddress(i), ComputeAddress(j), swapBuffer);
  619.             }
  620.             else
  621.                 return j;
  622.         }
  623.     }
  624.  
  625.     return 0;                                    // this return statement is never executed, but exists to defeat an xlC warning
  626. }
  627.  
  628. //----------------------------------------------------------------------------------------
  629. // TDynamicArray::QSRandomPartition: 
  630. //----------------------------------------------------------------------------------------
  631. #pragma segment ListRes
  632. ArrayIndex TDynamicArray::QSRandomPartition(ArrayIndex beginIndex,
  633.                                           // p
  634.                                           ArrayIndex endIndex,
  635.                                           // r
  636.                                           CompareElementsType CompareItems,
  637.                                           void* yourDataPtr,
  638.                                             void* swapBuffer)
  639. {
  640.     ArrayIndex i = RandomArrayIndex(beginIndex, endIndex);
  641.  
  642.     // exchange
  643.     SwapElements(ComputeAddress(beginIndex), ComputeAddress(i), swapBuffer);
  644.  
  645.     return QSPartition(beginIndex, endIndex, CompareItems, yourDataPtr, swapBuffer);
  646. }
  647.  
  648. //----------------------------------------------------------------------------------------
  649. // RandomArrayIndex: 
  650. //----------------------------------------------------------------------------------------
  651. ArrayIndex RandomArrayIndex(ArrayIndex beginIndex,
  652.                             ArrayIndex endIndex)
  653. {
  654.     if (beginIndex == endIndex)
  655.         return beginIndex;
  656.     ArrayIndex randomValue = rand() % labs(endIndex - beginIndex);
  657.  
  658.     return beginIndex + randomValue;
  659. }
  660.  
  661. //----------------------------------------------------------------------------------------
  662. // CompareObjects: 
  663. //----------------------------------------------------------------------------------------
  664. #pragma segment ListRes
  665.  
  666. CompareResult CompareElements(void* element1,
  667.                              void* element2,
  668.                              void* yourDataPtr)
  669. {
  670.     return ((TDynamicArray *)yourDataPtr)->CompareElements(element1, element2);
  671. }
  672.  
  673.  
  674. //========================================================================================
  675. // struct CElementInserter
  676. //========================================================================================
  677.  
  678. struct CElementInserter
  679. {
  680. public:
  681.     void*& fElementPtr;
  682.     TSortedDynamicArray* fDynamicArray;
  683.  
  684.     CElementInserter(void*& theElementPtr,
  685.                      TSortedDynamicArray* theDynamicArray) :
  686.         fElementPtr(theElementPtr),
  687.         fDynamicArray(theDynamicArray)
  688.     {
  689.     }
  690. };
  691.  
  692.  
  693. //----------------------------------------------------------------------------------------
  694. // TestItemForInsert: 
  695. //----------------------------------------------------------------------------------------
  696. #pragma segment ListRes
  697. CompareResult TestItemForInsert(ArrayIndex anItem,
  698.                                 void* yourDataPtr)
  699. {
  700.     CElementInserter * insertInfo = (CElementInserter *)yourDataPtr;
  701.     return insertInfo->fDynamicArray->CompareElements(insertInfo->fElementPtr, insertInfo->fDynamicArray->ComputeAddress(anItem));
  702. }
  703.  
  704.  
  705. //========================================================================================
  706. // CLASS TSortedDynamicArray
  707. //========================================================================================
  708. #undef Inherited
  709. #define Inherited TDynamicArray
  710.  
  711. #pragma segment ListNonRes
  712. MA_DEFINE_CLASS_M1(TSortedDynamicArray,
  713.                    Inherited);
  714.  
  715. //----------------------------------------------------------------------------------------
  716. // TSortedDynamicArray destructor
  717. //----------------------------------------------------------------------------------------
  718. #pragma segment MADestructorRes
  719.  
  720. TSortedDynamicArray::~TSortedDynamicArray()
  721. {
  722. }
  723.  
  724. //----------------------------------------------------------------------------------------
  725. // TSortedDynamicArray::DoSearchElement: DON'T use exit to get out of this routine from
  726. // your TestItem function or you will be really sad! (our debugger will check for you)
  727. // That's why you can return true to stop enumerating. Signaling Failure is OK too.
  728. //----------------------------------------------------------------------------------------
  729. #pragma segment ListRes
  730.  
  731. Boolean TSortedDynamicArray::DoSearchElement(CompareIndexType TestItem,
  732.                                              void* yourDataPtr,
  733.                                              ArrayIndex& index)
  734. {
  735.     Boolean found = FALSE;
  736.  
  737.     if (fSize == kEmptyIndex)
  738.         index = 1;
  739.     else
  740.     {
  741.         CompareResult aCompareResult;
  742.         CArrayIterator iter(this);
  743.  
  744.         do
  745.         {
  746.             // (fLowBound + fHighBound) / 2
  747.             iter.fCurrentIndex = (iter.fLowBound + iter.fHighBound) >> 1;
  748.  
  749.             aCompareResult = TestItem(iter.fCurrentIndex, yourDataPtr);
  750.  
  751.             if (aCompareResult <= kItemGreaterThanCriteria)
  752.                 iter.fHighBound = iter.fCurrentIndex - 1;
  753.             else
  754.                 iter.fLowBound = iter.fCurrentIndex + 1;
  755.  
  756.         } while (!((aCompareResult == kItemEqualCriteria) || (iter.fLowBound > iter.fHighBound)));
  757.  
  758.         if (aCompareResult == kItemEqualCriteria)
  759.             found = TRUE;
  760.         else if (aCompareResult >= kItemLessThanCriteria)
  761.             ++iter.fCurrentIndex;
  762.  
  763.         // keep index in range 
  764.         index = ((iter.fCurrentIndex < 1) || (iter.fCurrentIndex > fSize + 1)) ? kEmptyIndex : iter.fCurrentIndex;
  765.  
  766.     }
  767.  
  768.     return found;
  769. }
  770.  
  771. //----------------------------------------------------------------------------------------
  772. // TSortedDynamicArray::InsertElementInOrder: 
  773. //----------------------------------------------------------------------------------------
  774. #pragma segment ListRes
  775. void TSortedDynamicArray::InsertElementInOrder(void* elementPtr)
  776. {
  777.     ArrayIndex index;
  778.     CElementInserter anElementInserter(elementPtr, this);
  779.  
  780.     DoSearchElement(&TestItemForInsert, &anElementInserter, index);
  781.     InsertElementsBefore(index, elementPtr, 1);
  782. }
  783.  
  784. //----------------------------------------------------------------------------------------
  785. // End of UDynamicArray.cp
  786.  
  787. #pragma segment Inline
  788.